package leetcodev1.数组;

import java.util.*;

public class LeetCode56 {

    //官方答案，简洁明了
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int[] interval : intervals) {
            int L = interval[0], R = interval[1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }

    //输入 [[1,3],[2,6],[8,10],[15,18]]
    //输出 [[1,6],[8,10],[15,18]]
    //思路根据start进行排序
    //排序后进行i+1合并 不能合并的更换指针
    //写的有点稚嫩
    public int[][] merge1(int[][] intervals) {
        List<Interval> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(new Interval(interval[0], interval[1]));
        }

        Collections.sort(list);
        int index = 1;
        Interval current = list.get(0);
        List<Interval> retList = new ArrayList<>();
        while (index < intervals.length) {
            Interval tmp = list.get(index);
            if (tmp.startIndex <= current.endIndex) {
                //合并区间
                current.endIndex = Math.max(current.endIndex, tmp.endIndex);
            } else {
                //否则重置指针位置
                retList.add(current);
                current = tmp;
            }
            index++;
        }

        if (retList.size() == 0 || retList.get(retList.size() - 1) != current) {
            retList.add(current);
        }

        int[][] ret = new int[retList.size()][2];
        for (int i = 0; i < retList.size(); i++) {
            ret[i][0] = retList.get(i).startIndex;
            ret[i][1] = retList.get(i).endIndex;
        }
        return ret;
    }

    //由小到大排序
    class Interval implements Comparable {
        public int startIndex;
        public int endIndex;

        public Interval(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        @Override
        public int compareTo(Object o) {
            Interval interval = (Interval) o;
            return this.startIndex - interval.startIndex;
        }
    }
}
